// 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

// 现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

// 求所能获得硬币的最大数量。

// 说明:

// 你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
// 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
// 示例:

// 输入: [3,1,5,8]
// 输出: 167 
// 解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
//      coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

#include <vector>

using namespace std;

/* 记忆化数组
倒过来看这些操作，将全过程看作是每次添加一个气球。
solve(i,j) 表示将开区间 (i,j) 内的位置全部填满气球能够得到的最多硬币数
时间复杂度：O(n^3)
空间复杂度：O(n^2)
*/
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vals.resize(n + 2, 1); // 预处理，新建一个数组，两端加上1
        for (int i{1}; i <= n; ++i) {
            vals[i] = nums[i-1];
        }
        records.resize(n + 2, vector<int>(n + 2, -1));
        return solve(0, n + 1);
    }
    // 开区间(left, right)
    int solve(int left, int right) {
        if (left >= right - 1) return 0;
        if (records[left][right] != -1) return records[left][right];
        for (int i{left + 1}; i < right; ++i) {
            int sum = vals[left] * vals[i] * vals[right];
            sum += solve(left, i) + solve(i, right);
            if (sum > records[left][right]) records[left][right] = sum;
        }
        return records[left][right];
    }
private:
    vector<vector<int>> records{};
    vector<int> vals{};
};

/* 动态规划
我们可以通过变换计算顺序，从「自顶向下」的记忆化搜索变为「自底向上」的动态规划。
令 dp[i][j] 表示填满开区间 (i,j)(i,j) 能得到的最多硬币数，那么边界条件是 i≥j−1，此时有 dp[i][j]=0。
时间复杂度：O(n^3)
空间复杂度：O(n^2)
*/
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        vector<int> vals(n + 2, 1);
        for (int i{1}; i <= n; ++i) {
            vals[i] = nums[i-1];
        }
        for (int i{n - 1}; i >= 0; --i) {
            for (int j{i + 2}; j <= n + 1; ++j) {
                for (int k{i + 1}; k < j; ++k) {
                    int sum = vals[i] * vals[k] * vals[j];
                    sum += dp[i][k] + dp[k][j];
                    if (sum > dp[i][j]) dp[i][j] = sum;
                }
            }
        }
        return dp[0][n + 1];
    }
};